package com.faiz.algorithm;

import java.util.ArrayList;
import java.util.List;

public class ReverseKGroup {
    public ListNode reverseKGroup(ListNode head, int k) {
        return reverseKGroup(head, k, 1);
    }

    // 最简单的方法，直接交换链表的值
    private final List<Integer> nums = new ArrayList<>();
    // 标记哪一个部分不需要翻转
    private int noReverse = -1;

    private ListNode reverseKGroup(ListNode head, int k, int n) {
        if (head == null) {
            if (0 != nums.size() % k) {
                noReverse = nums.size() / k;
            }
            return null;
        }

        nums.add(head.val);
        reverseKGroup(head.next, k, n + 1);
        // 不改变顺序, 直接返回就行
        int quotient = (n - 1) / k;
        int remainder = (n - 1) % k;
        if (quotient < noReverse) {
            head.val = nums.get(quotient * k - 1 + (k - remainder));
        }
        return head;
    }

    // 迭代翻转链表（头插法）
    private ListNode reverseList(ListNode left, ListNode right) {
        // 构造哑节点
        ListNode dummy = new ListNode(555);
        dummy.next = left;

        ListNode g = dummy, p = left;

        while (p.next != right) {
            ListNode remove = p.next;
            p.next = p.next.next;

            remove.next = g.next;
            g.next = remove;
        }
        return dummy.next;
    }




    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};

        ListNode head = new ListNode.Builder(nums).build();
        ReverseKGroup reverseKGroup = new ReverseKGroup();
        System.out.println("hello");
    }
}
